\(k\) -means 방법

\(k\) – means 방법은 다변량 자료를 클러스터링을 하는 가장 대표적인 방법이다. 개념은 간단하다. \(k\) 개의 평균이 있고, 이 평균은 모두 서로 다른 집단을 나타낸다. 모든 자료는 가장 가까운 평균에 소속된다.

가우시안 혼합 모형(GMM: Gaussian Mixture Model)

1변수 두 집단의 가우시안 혼합 모형은 다음과 같다.

\[f(X=x|\mu_1, \sigma_1, \mu_2, \sigma_2) = w_1\frac{1}{\sigma_1\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_1}{\sigma_1})^2\right] + w_2\frac{1}{\sigma_2\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_2}{\sigma_2})^2\right]\]

여기서 \(\mu_1\) , \(\mu_2\) 는 두 집단의 평균이고, \(\sigma_1\) , \(\sigma_2\) 는 두 집단의 표준편차이다. 그리고 \(w_1\) 과 \(w_2\) 는 각 집단의 비율을 나타낸다.

만약 1변수가 아니라 다변수의 자료를 다룬다면 \(x\) 는 \(\vec{x}\) 로, \(\mu_1\) 는 \(\vec{\mu_1}\) , \(\sigma_1\) 은 \(\Sigma_1\) (분산-공분산 행렬)로 나타내야 할 것이다. 만약 집단이 여럿이라면 \(w_3\frac{1}{\sigma_3\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_3}{\sigma_3})^2\right]\) 가 추가된다.

\(k\) -means와 GMM의 차이

\(k\) -평균과 GMM은 비슷하다. 여러 집단이 있고, 이 집단은 평균으로 구분된다. 하지만 \(k\) -평균에는 분산이 없다. 그리고 모든 사례는 하나의 집단에 소속된다. (반면 GMM에서 한 사례는 보통 여러 집단에 확률적으로 소속된다.)

사실 PRML에서 Bishop이 얘기했듯이 GMM에서 모든 집단의 분산을 \(\sigma\textbf{I}\) ( \(\sigma \rightarrow 0\) )으로 무한히 축소시키면 GMM은 \(k\) -평균과 같아진다.

이는 다음과 같이 확인할 수 있다. 다음은 각 사례의 소속이 결정되었을 때 확률변수 \(X\) 의 확률분포를 나타낸다.

\[f_1(X=x|\mu_1, \sigma_1) = \frac{1}{\sigma_1\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_1}{\sigma_1})^2\right]\]

\[f_2(X=x|\mu_2, \sigma_2) = \frac{1}{\sigma_2\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_2}{\sigma_2})^2\right]\]

어떤 사례 \(x\) 가 주어졌을 때, \(f_1(x)\) 와 \(f_2(x)\) 을 비교하여 \(x\) 의 소속을 결정한다고 해보자. 베이지안으로 생각하면 \(P(g=1 |x) = P(x|g=1)P(g=1)/P(x)\) 이고 이는 다음과 같이 풀어 쓸 수 있다.

\[P(g=1|x)= \frac{P(x|g=1)P(g=1)}{P(x)} = \frac{f_1(X=x)P(g=1)}{f_1(x)P(g=1)+f_2(x)P(g=2)}\]

여기서 분자, 분모에 공통인 \(f_1(x)P(g=1)\) 을 나눠주면,

\[P(g=1|x)= \frac{1}{1+f_2(x)P(g=2)/f_1(x)P(g=1)}\]

\(\frac{1}{1+x}\) 의 그래프는 다음과 같다. ( \(f_2(x)P(g=2)/f_1(x)P(g=1)\) 는 양수임을 주목하자.)

curve(1/(1+x), xlim=c(0,3))

이때 만약 \(\sigma_1\) 과 \(\sigma_2\) 가 모두 \(0\) 과 매우 가까워진다면 \(f_2(x)/f_1(x)\) 는 다음과 같다.

\[\frac{f_2(x)}{f_1(x)} = \frac{\frac{1}{\sigma_2\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_2}{\sigma_2})^2\right]}{\frac{1}{\sigma_1\sqrt{2\pi}}\exp\left[-\frac{1}{2}(\frac{x-\mu_1}{\sigma_1})^2\right]}\]

여기서 \(\frac{\sigma_1}{\sigma_2} \approx 1\) 로 생각하면 위의 식은 다음과 같이 정리된다.

\[\frac{f_2(x)}{f_1(x)} = \exp\left[-\frac{1}{2}[(\frac{x-\mu_2}{\sigma_2})^2-(\frac{x-\mu_1}{\sigma_1})^2]\right]\]

\[\phantom{\frac{f_2(x)}{f_1(x)}} = \exp\left[-\frac{1}{2}\frac{-2(\mu_2-\mu_1)x+\mu_2^2-\mu_1^2}{\sigma_1^2}\right]\]

\[\phantom{\frac{f_2(x)}{f_1(x)}} = \exp\left[-\frac{1}{2}\frac{-2(\mu_2-\mu_1)(x-(\mu_1+\mu_2)/2)}{\sigma_1^2}\right]\]

\(\mu_1 \neq \mu_2\) 이고, \(\sigma_1^2 > 0\) 이므로, \(\exp\) 안의 부호는 \(x-(\mu_1+\mu_2)/2\) 의 부호에 의해 결정되는데, 만약 \(x-(\mu_1+\mu_2)/2 > 0\) 이라면, \(\exp\) 안은 \(\infty\) 가 된고, \(\frac{f_2(x)}{f_1(x)}\) 역시 무한대가 된다. 반대로 \(x-(\mu_1+\mu_2)/2 < 0\) 라면, \(\frac{f_2(x)}{f_1(x)}\) 은 \(0\) 이 된다.

따라서 \(P(g=1)\) 과 \(P(g=2)\) 에 상관없이(0보다 크고, 상수라면) \(P(g=1|x)\) 은 \(1\) 또는 \(0\) 이 되어, 흔히 말하는 hard assignment가 된다. 그리고 소속은 조금이라도 가까운 평균의 소속이 된다.

그런데 솔직히 어떤 집단의 생성 분포가 가우시안일 때 분산이 0인 경우가 얼마나 되겠나? (그리고 분산이 0이라면 데이터는 거의 확실히 평균과 동일해야 하지 않은가?) 따라서 \(k\) -평균 모형은 확률 모형으로 생각했을 때 조금은 지나치게 제약적이며, 비현실적인 모형이라고 할 수 있다.

그럼에도 \(k\) -means 가 심심치 않게 쓰이는 것은 무슨 연유일까요?

1. 계산 속도가 빨라서
2. 남들이 많이 쓰니까
3. GMM을 써 본 적이 없어서